package 数据结构.堆.数组堆.最大堆;

import 数据结构.数组.Array;

/**
 * @author Veng Su 1344114844@qq.com
 * @date 2018/7/25 15:28
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E > data;
    public MaxHeap( int capacity){
        data=new Array<>(capacity);
    }
    public MaxHeap(){
        data=new Array<>();
    }

    /**
     * 将一个数组转换成最大堆
     * @param arr
     */
    public MaxHeap(E[] arr){
        data=new Array<>(arr);
        for (int i =parent(arr.length-1); i >+0 ; i--) {
            siftDown(i);
        }
    }

    /**
     * 将一个数组转换成最大堆
     * @param arr
     * @return
     */
    public  MaxHeap heapify(E[] arr){
        data=new Array<>(arr);
        for (int i =parent(arr.length-1); i >+0 ; i--) {
            siftDown(i);
        }
        return this;
    }
    /**
     * 返回堆中元素个数
     */
    public int size(){
        return data.getSize();
    }

    /**
     * 判定对重元素是否为空
     * @return true 为空
     */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    /**
     * 返回父亲结点的索引值
     * @param index
     * @return 索引值
     */
    private int parent(int index){
        if (index==0){
            throw new IllegalArgumentException("根节点没有父亲结点");
        }
        return (index-1)/2;
    }

    /**
     * 返回当前节点的右孩子的节点的索引值
     * @param index
     * @return 索引值
     */
    private int rightChild(int index){
        return index*2+2;
    }

    /**
     * 返回当前节点的左孩子的结点的索引值
     * @param index
     * @return 索引值
     */
    private int leftChild(int index) {
        return index*2+1;
    }

    /**
     * 添加一个元素
     * @param e
     */
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    /**
     * 元素上浮
     * @param k
     */
    private void siftUp(int k) {
        while (k>0&&(data.get(parent(k))).compareTo(data.get(k))<0){
            data.swap(k,parent(k));
            k=parent(k);
        }
    }

    /**
     * 取出最大的元素
     * @return 最大的元素
     */
    public E extractMax(){
        E ret=findMax();
        data.swap(0,data.getSize()-1);
        data.removeLast();
        siftDown(0);
        return ret;

    }

    /**
     * 元素下沉
     * @param k
     */
    private void siftDown(int k) {
        while (leftChild(k)<data.getSize()){
            int j=leftChild(k);
            if (j+1<data.getSize()&&data.get(j+1).compareTo(data.get(j))>0){
                j=rightChild(k);
            }
            if (data.get(k).compareTo(data.get(j))>=0){
                break;
            }else {
                data.swap(k,j);
                k=j;
            }
        }
    }
    /**
     * 找到最大的元素
     * @return 最大的元素
     */
    public E findMax(){
        if (data.getSize()==0){
            throw new IllegalArgumentException("heap 为空");
        }
        return data.get(0);
    }
    public E replace(E e){
        E ret=findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }
}
